package com.demo.datastructure.reorder.mergeSort;

import com.demo.datastructure.reorder.Example;

/**
 * @author ljr
 * @version 1.0
 * @description: 自顶向下的原地归并排序
 * @date 2021/9/18 20:31
 */
public class SimpleMergeSort implements Example {

    @Override
    public void sort(Comparable[] a, int low, int high) {
        if(low >= high) return;
        int mid = low + (high-low >> 1);
        sort(a, low, mid);
        sort(a, mid+1, high);
        merge(a, low, mid, high);
    }

    private void merge(Comparable[] a, int low, int mid, int high) {
        int length = high-low+1;
        Comparable[] newA = new Comparable[length];

        int l = low, h = mid+1;
        for(int i = 0; i < length; i++){
            if(l > mid)  newA[i] = a[h++];
            else if(h > high)  newA[i] = a[l++];
            else if(less(a[l], a[h])) newA[i] = a[l++];
            else newA[i] = a[h++];
        }

        for(int i = 0; i < length; i++){
            a[low++] = newA[i];
        }
    }


    private void merge2(Comparable[] a, int low, int mid, int high) {
         Comparable[] lefts = new Comparable[mid-low+2];
         Comparable[] rights = new Comparable[high-mid+1];

         int l = low, h=mid+1;
         for(int i = 0; i < lefts.length-1; i++){
             lefts[i] = a[l++];
         }
        lefts[lefts.length-1] = Integer.MAX_VALUE;

        for(int i = 0; i < rights.length-1; i++){
            rights[i] = a[h++];
        }
        rights[rights.length-1] = Integer.MAX_VALUE;

        l = 0;
        h = 0;
        for(int i = low; i <= high; i++){
            if(less(lefts[l],rights[h])){
                a[i] = lefts[l++];
            }else{
                a[i] = rights[h++];
            }
        }
    }


    private void merge3(Comparable[] a, int low, int mid, int high) {
        int i =  low, j = mid+1;
        Comparable[] aux = new Comparable[high+1];
        for(int k = low; k <= high; k++)
            aux[k] = a[k];

        for(int k = low; k <= high; k++){
            if(i > mid) a[k] = aux[j++];
            else if(j > high) a[k] = aux[i++];
            else if(less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }
}

